Leetcode - 1776 Car Fleet II

Posted on | In ,

In the discussion of this problem, most people said we can use monostack to solve it. However, they didn’t tell us why. Here I want to give an explanation with more details.

Solution

leetcode1776-1.jpeg
leetcode1776-2.jpeg

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
    // [1,2], [2,1], [4,3], [7,2]
    // 2nd&3rd car collide, then first car 
    // brute force O(n^2)
    // [7, 2], 
    vector<double> getCollisionTimes(vector<vector<int>>& cars) {
        // k-1 times in stack
        stack<double> intersectionTime;
        // k cars in stack
        stack<int> carsInStack;
        int n = cars.size();
        vector<double> ans;
        for(int i = n-1;i >= 0;i--) {
            while(!intersectionTime.empty()) {
                int indexOfTopCar = carsInStack.top();
                // [1,5], [3, 10] 2/10-5
                if(cars[indexOfTopCar][1]==cars[i][1]) {
                    carsInStack.pop();
                    intersectionTime.pop();
                    continue;
                }
                double collideTime = ((double)cars[indexOfTopCar][0]-cars[i][0])/(cars[i][1]-cars[indexOfTopCar][1]);
                if(collideTime <= 0) {
                    carsInStack.pop();
                    intersectionTime.pop();
                } else {
                    if(collideTime>intersectionTime.top()) {
                        carsInStack.pop();
                        intersectionTime.pop();
                    } else {
                        carsInStack.push(i);
                        intersectionTime.push(collideTime);
                        ans.push_back(collideTime);
                        break;
                    }
                }
            }
            if(intersectionTime.empty()&&carsInStack.size()==1) {
                int indexOfTopCar = carsInStack.top();
                if(cars[indexOfTopCar][1]==cars[i][1]) {
                    carsInStack.pop();
                    carsInStack.push(i);
                    ans.push_back(-1.0);
                } else {
                    // 3/1
                    double collideTime = ((double)cars[indexOfTopCar][0]-cars[i][0])/(cars[i][1]-cars[indexOfTopCar][1]);
                    if(collideTime <= 0) {
                        carsInStack.pop();
                        carsInStack.push(i);
                        ans.push_back(-1.0);
                    } else {
                        intersectionTime.push(collideTime);
                        carsInStack.push(i);
                        ans.push_back(collideTime);
                    }
                }
            } else if(intersectionTime.empty()&&carsInStack.empty()) {
                carsInStack.push(i);
                ans.push_back(-1.0);
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};